题解 CF1407C@洛谷 | 1407C@Codeforces 【Chocolate Bunny】

交互题最好玩♂了！（雾）

题意简述：有一个 $n$ 个数的排列，每次询问 $x,y$ 得到 $a_x\bmod a_y$ 的值，最多使用 $2\times n$ 次询问，猜出这个序列。

思路：

看到最多 $2\times n$ 次询问，我们想到了什么？凭我们的直觉，这就是明摆着的提示要询问 $i,j$ 和 $j,i$ 啊！那怎么询问呢？

我们知道对于 $a\lt b$，$a\bmod b=a$，可以得到下面结论：

结论：$(a\bmod b\gt b\bmod a)\iff (a\lt b)$。

简单证明：

$\begin{aligned} \operatorname{if}\ a\gt b\ &\operatorname{then}\ (a\bmod b)\lt(b\bmod a)=b\\ \operatorname{if}\ a=b\ &\operatorname{then}\ (a\bmod b)=(b\bmod a)=0\\ \operatorname{if}\ a\lt b\ &\operatorname{then}\ (b\bmod a)\lt(a\bmod b)=a \end{aligned}$

在知道这个性质之后，我们就可以想到询问的方法：

设 $ma$ 为 $a_1\sim a_i$ 中最大的数的下标（大小可根据上面的结论判断），每次询问 $ma,i$ 和 $i,ma$，判断两个结果哪个更大，更新偏小的那个下标的值及最大数的下标。

最后剩下一个 $a_{ma}$ 没有值，由于数列是 $1\sim n$ 的一个排列，因此这个最大的数就是 $n$。

总询问次数 $2\times n-2$。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;

int n, a[N], ma = 1;

int ask(int x, int y) {
	int _;
	printf("? %d %d\n", x, y);
	fflush(stdout);
	scanf("%d", &_);
	return _;
}

int main() {
	scanf("%d", &n);
	for(int i=2;i<=n;i++) {
		int _1 = ask(ma, i);
		int _2 = ask(i, ma);
		if(_1 > _2) {
			a[ma] = _1;
			ma = i;
		}
		else a[i] = _2;
	}
	a[ma] = n;
	putchar('!');
	for(int i=1;i<=n;i++) printf(" %d", a[i]);
	return 0;
}